#include <iostream>

template<typename DT>
class Node
{
private:
    DT element;
public:
    virtual DT getElemnt() const {return element;}
    virtual void setElemnt(DT _val) {element = _val;}
    Node(DT _val) {element = _val;}
};

/**
 BinaryTree
*/
template<typename DT>
class BinaryTree
{
public:
    virtual void insert(DT _val) = 0;
    virtual void remove(DT _val) = 0;
};


/**
 BinarySearchTree
*/
template<typename DT>
class BST: public BinaryTree<DT> //继承BinaryTree
{
private:
    class BSTNode: public Node<DT> 
    {
    private:
        BSTNode *left;
        BSTNode *right;
        int depth;		/** Depth of the node. */
    };

    BSTNode(DT _val): Node<DT>(_val)
    {
        left = nullptr;
        right = nullptr;
    }
    BSTNode* root;

public:
    BST() {}
    BST(DT _val){}
    ~BST(){};
    virtual void findmin(DT _val){};  //查找最小值
    virtual void find(DT _val){};  //查找是否有值为_val的值
    void printTree( ) const{};  //中序遍历打印所有节点
};

/**
AvlTree
*/
template<typename DT>
class AvlTree: public BST<DT>
{
private:
    class AvlNode: public Node<DT>
    {
    private:
        AvlNode *left;
        AvlNode *right;
        int depth;		//Depth of the node. 
        int height;
    };
    AvlNode(DT _val): Node<DT>(_val)
    {
        left = nullptr;
        right = nullptr;
    }
    AvlNode* root;

public:
    AvlTree() {};
    ~AvlTree() {};
    void balance( AvlNode * & t ) {};
    void rotateWithLeftChild( AvlNode * & k2 ) {};
    void rotateWithRightChild( AvlNode * & k1 ) {};
    void doubleWithLeftChild( AvlNode * & k3 ) {};
    void doubleWithRightChild( AvlNode * & k1 ) {};
};

/**
SplayTree
*/
template<typename DT>
class SplayTree: public BST<DT>
{
private:
    class SplayNode: public Node<DT>
    {
    private:
        SplayNode parent; 
        SplayNode left;
        SplayNode right;
        int depth;		//Depth of the node. 
        int height;
    };
    SplayNode() 
    {
        parent=NULL;
        left=nullptr;
        right=nullptr;
    }
    SplayNode* root;
public:
    SplayTree() {};
    ~SplayTree() {};
    void zig_zag(SplayNode * & k1 ); //之字形情况旋转
    void zig_zig(SplayNode * & k1 ); //一字形情况旋转
};


